<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 回溯法的核心框架
      // for 选择 in 选择列表:
      // # 做选择
      // 将该选择从选择列表移除
      // 路径.add(选择)
      // backtrack(路径, 选择列表)
      // # 撤销选择
      // 路径.remove(选择)
      // 将该选择再加入选择列表
      let res = [];
      var permuteUnique = function (nums) {
        // 方法一：回溯（）---时间：O（）（不会算，至少是n!，要回溯递归）---空间：O（）（不会算，至少是n，递归栈的深度）
        nums.sort();
        let used = new Array(nums.length).fill(false);
        let track = [];

        // 通过记录上一个节点去重
        let preNum = 666

        backtrack(nums, track, used);
        return res;
      };

      function backtrack(nums, track, used) {
        if (track.length === nums.length) {
          // 这样写可以，但是花的时间太久了
          // let flag = true;
          // for (let i = 0; i < res.length; i++) {
          //   if (res[i].join("") === track.join("")) {
          //     flag = false;
          //     break;
          //   } else {
          //     flag = true;
          //   }
          // }
          // if (flag) {
          res.push([...track]);
          return;
          // }
        }
        for (let i = 0; i < nums.length; i++) {
          if (used[i]) {
            continue;
          }
          // 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
          // 都行，但是上面这个效率高些
          // if (nums[i] == nums[i - 1] && !used[i - 1]) {
          if (nums[i] == nums[i - 1] && used[i - 1]) {
            // 如果前面的相邻相等元素没有用过，则跳过
            // 也就是说只有前面的相等元素用过了才可以组合后面的，也就固定了元素在排列中的相对位置
            continue;
          }
          track.push(nums[i]);
          // 做选择
          // 将该选择从选择列表移除
          used[i] = true;
          backtrack(nums, track, used);
          // 撤销选择
          // 将该选择再加入选择列表
          track.pop();
          used[i] = false;
        }
      }

      // console.log(permuteUnique([1, 1, 0, 0, 1, -1, -1, 1]));
      // console.log(permuteUnique([3,3,0,3]));
      console.log(permuteUnique([1,1,2]));
    </script>
  </body>
</html>
